<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
<meta name="viewport"
      content="width=device-width, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">

    <meta name="author" content="Mouweng">





<title>彻底搞懂红黑树 | Mouweng&#39;s Blog</title>



    <link rel="icon" href="/favicon.ico">




    <!-- stylesheets list from _config.yml -->
    
    <link rel="stylesheet" href="/css/style.css">
    



    <!-- scripts list from _config.yml -->
    
    <script src="/js/script.js"></script>
    
    <script src="/js/tocbot.min.js"></script>
    



    
    
        
    


<meta name="generator" content="Hexo 5.1.1"><link rel="alternate" href="/atom.xml" title="Mouweng's Blog" type="application/atom+xml">
</head>
<body>
    <div class="wrapper">
        <header>
    <nav class="navbar">
        <div class="container">
            <div class="navbar-header header-logo"><a href="/">Mouweng</a></div>
            <div class="menu navbar-right">
                
                    <a class="menu-item" href="/archives">Posts</a>
                
                    <a class="menu-item" href="/category">Categories</a>
                
                    <a class="menu-item" href="/tag">Tags</a>
                
                    <a class="menu-item" href="/about">About</a>
                
                <input id="switch_default" type="checkbox" class="switch_default">
                <label for="switch_default" class="toggleBtn"></label>
            </div>
        </div>
    </nav>

    
    <nav class="navbar-mobile" id="nav-mobile">
        <div class="container">
            <div class="navbar-header">
                <div>
                    <a href="/">Mouweng</a><a id="mobile-toggle-theme">·&nbsp;Light</a>
                </div>
                <div class="menu-toggle" onclick="mobileBtn()">&#9776; Menu</div>
            </div>
            <div class="menu" id="mobile-menu">
                
                    <a class="menu-item" href="/archives">Posts</a>
                
                    <a class="menu-item" href="/category">Categories</a>
                
                    <a class="menu-item" href="/tag">Tags</a>
                
                    <a class="menu-item" href="/about">About</a>
                
            </div>
        </div>
    </nav>

</header>
<script>
    var mobileBtn = function f() {
        var toggleMenu = document.getElementsByClassName("menu-toggle")[0];
        var mobileMenu = document.getElementById("mobile-menu");
        if(toggleMenu.classList.contains("active")){
           toggleMenu.classList.remove("active")
            mobileMenu.classList.remove("active")
        }else{
            toggleMenu.classList.add("active")
            mobileMenu.classList.add("active")
        }
    }
</script>
        <div class="main">
            <div class="container">
    
    
        <div class="post-toc">
    <div class="tocbot-list">
    </div>
    <div class="tocbot-list-menu">
        <a class="tocbot-toc-expand" onclick="expand_toc()">Expand all</a>
        <a onclick="go_top()">Back to top</a>
        <a onclick="go_bottom()">Go to bottom</a>
    </div>
</div>

<script>
    document.ready(
        function () {
            tocbot.init({
                tocSelector: '.tocbot-list',
                contentSelector: '.post-content',
                headingSelector: 'h1, h2, h3, h4, h5',
                collapseDepth: 1,
                orderedList: false,
                scrollSmooth: true,
            })
        }
    )

    function expand_toc() {
        var b = document.querySelector(".tocbot-toc-expand");
        tocbot.init({
            tocSelector: '.tocbot-list',
            contentSelector: '.post-content',
            headingSelector: 'h1, h2, h3, h4, h5',
            collapseDepth: 6,
            orderedList: false,
            scrollSmooth: true,
        });
        b.setAttribute("onclick", "collapse_toc()");
        b.innerHTML = "Collapse all"
    }

    function collapse_toc() {
        var b = document.querySelector(".tocbot-toc-expand");
        tocbot.init({
            tocSelector: '.tocbot-list',
            contentSelector: '.post-content',
            headingSelector: 'h1, h2, h3, h4, h5',
            collapseDepth: 1,
            orderedList: false,
            scrollSmooth: true,
        });
        b.setAttribute("onclick", "expand_toc()");
        b.innerHTML = "Expand all"
    }

    function go_top() {
        window.scrollTo(0, 0);
    }

    function go_bottom() {
        window.scrollTo(0, document.body.scrollHeight);
    }

</script>
    

    
    <article class="post-wrap">
        <header class="post-header">
            <h1 class="post-title">彻底搞懂红黑树</h1>
            
                <div class="post-meta">
                    
                        Author: <a itemprop="author" rel="author" href="/">Mouweng</a>
                    

                    
                        <span class="post-time">
                        Date: <a href="#">August 27, 2020&nbsp;&nbsp;23:41:12</a>
                        </span>
                    
                    
                        <span class="post-category">
                    Category:
                            
                                <a href="/categories/%E5%85%B6%E4%BB%96/">其他</a>
                            
                        </span>
                    
                </div>
            
        </header>

        <div class="post-content">
            <p><a target="_blank" rel="noopener" href="https://blog.csdn.net/v_july_v/category_774945.html">本篇参考专栏</a>（虽然是一个系列，个人觉得讲的不是很清晰）</p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/qq_37169817/article/details/78880110">红黑树的删除主要参考此博客</a>（删除系列讲得很好）</p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/qq_32924343/article/details/80927514">红黑树删除全过程化</a>（删除练习）</p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/v_JULY_v/article/details/6284050">红黑树从头至尾插入和删除结点的全程演示图</a>（插入与删除练习）</p>
<p><a target="_blank" rel="noopener" href="https://www.cs.usfca.edu/~galles/visualization/RedBlack.html">红黑树演示动画参考</a></p>
<h3 id="红黑树的定义"><a href="#红黑树的定义" class="headerlink" title="红黑树的定义"></a>红黑树的定义</h3><p>一棵特殊（带颜色）的二叉查找树，如果所有结点都变为黑色，就是一棵二叉查找树</p>
<h3 id="红黑树的性质"><a href="#红黑树的性质" class="headerlink" title="红黑树的性质"></a>红黑树的性质</h3><p>（1）每个节点或者是黑色，或者是红色。<br>（2）根节点是黑色。<br>（3）每个叶子节点（NIL）是黑色。 [这里叶子节点，是指为空NIL的叶子节点！]<br>（4）如果一个节点是红色的，则它的子节点必须是黑色的。<br>（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。</p>
<h3 id="红黑树调整"><a href="#红黑树调整" class="headerlink" title="红黑树调整"></a>红黑树调整</h3><p>所以为了使插入、或删除结点后的树依然维持为一棵新的红黑树，需要：</p>
<ol>
<li>变色</li>
<li>旋转（左旋、右旋）</li>
</ol>
<h3 id="插入"><a href="#插入" class="headerlink" title="插入"></a>插入</h3><hr>
<p><strong>情形1: 新节点N位于树的根上，没有父节点；</strong></p>
<ul>
<li>把根节点设为黑色</li>
</ul>
<p><strong>情形2:</strong> <strong>新节点的父节点P是黑色；</strong></p>
<ul>
<li>直接插入</li>
</ul>
<p><strong>情形3:父节点P、叔叔节点U，都为红色；</strong></p>
<ul>
<li>黑爸黑叔红祖父</li>
</ul>
<p><strong>情形4: 父节点P是红色，叔叔节点U是黑色或NIL；</strong> </p>
<p>​    <strong>4.1 插入节点N是其父节点P的右孩子，而父节点P又是其父节点的左孩子。（三角形、左旋）</strong></p>
<ul>
<li>以父节点作为左旋</li>
</ul>
<p>​    <strong>4.2 插入节点N 是其父节点的左孩子，而父节点P又是其父G的左孩子。（直线型、右旋）</strong></p>
<ul>
<li>把父节点变为黑色，把祖父节点变为红色，以祖父结点作为右旋</li>
</ul>
<p><strong>口诀</strong></p>
<blockquote>
<p>我根我爸黑，那就很简单</p>
<p>我爸红，叔也红，黑爸黑叔红祖父</p>
<p>我爸红，叔若黑，三角左旋转直线，直线右旋色互换</p>
</blockquote>
<p><strong>例子</strong></p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1g9ikqo9he3j31jm0u04qp.jpg"></p>
<h3 id="删除"><a href="#删除" class="headerlink" title="删除"></a>删除</h3><hr>
<h4 id="二叉搜索树的删除"><a href="#二叉搜索树的删除" class="headerlink" title="二叉搜索树的删除"></a>二叉搜索树的删除</h4><p>介绍RBT的删除，就先要知道二叉搜索树的删除(知道的同学可以直接跳过)。</p>
<p>删除分为四步：<br>1.找到删除点假设为X<br>2.找到X的代替点D，这里代替点可以有两个：一个是X左子树的最大点，也就是X左子树的最右点(也就是前驱点)；另外一种就是X的右子树的最小点，也就是X的右子树的最左变点(也就是后继点)。<br>3.将X的值改成为代替点D。<br>4.如果代替点有子节点，那么，删除代替点，并用其子节点接上这个缺口；如果无子节点，则直接删除。</p>
<h4 id="先来看看RBT的定义"><a href="#先来看看RBT的定义" class="headerlink" title="先来看看RBT的定义"></a>先来看看RBT的定义</h4><p>（1）每个节点或者是黑色，或者是红色。<br>（2）根节点是黑色。<br>（3）每个叶子节点（NIL）是黑色。 [这里叶子节点，是指为空NIL的叶子节点！]<br>（4）如果一个节点是红色的，则它的子节点必须是黑色的。<br>（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。</p>
<p><strong>比较重要的是4、5, BRT所做的操作很多都是为了满足4.5条属性。因此一定要记住！</strong></p>
<p>1.删除节点，也就是最简单的二叉搜索树的删除操作，只不过除了使用代替的值D替换被删除点的值X以外，还要保证原X点的颜色不变。<br>2.调整节点颜色，使得满足RBT的5个属性(主要是4,5）。</p>
<h4 id="RBT的删除Case讨论"><a href="#RBT的删除Case讨论" class="headerlink" title="RBT的删除Case讨论"></a>RBT的删除Case讨论</h4><p>假设我们使用了<strong>后继</strong>的方法完第一步删除节点的操作。并且用D表示要删除的代替点，P表示D的Parent，S表示D的Sister，SL、SR表示LeftTree和RigthTree，DR表示D的DR（DL一定是NIL）。</p>
<p>我们对D、DR、P、S、SL、SR做了颜色的讨论。（以下颜色只是随便给的，不用参考）</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1g9ihhwajnbj30r60hcdlf.jpg"></p>
<blockquote>
<p>case1：D是红色，DR为NIL</p>
<p>case2：D是黑色： </p>
<ul>
<li><p>case2-1：D是黑色，DR不为NIL，必为红色</p>
</li>
<li><p>case2-2：D是黑色，DR为NIL</p>
<ul>
<li>case2-2-1： case2-2条件+S节点为红色</li>
<li>case2-2-2： case2-2条件+S节点为黑色<ul>
<li>case2-2-2-1：case2-2-2 + P不能确定，SL为红色，SR任意(红色orNIL)</li>
<li>case2-2-2-2：case2-2-2 + P不能确定，SL为任意(红色orNIL)，SR红色</li>
<li>case2-2-2-3：case2-2-2 + P为红色，SL为黑色(NIL)，SR黑色(NIL)</li>
<li>case2-2-2-4：case2-2-2 + P为黑色，SL为黑色(NIL)，SR黑色(NIL)</li>
</ul>
</li>
</ul>
</li>
</ul>
</blockquote>
<hr>
<p><strong>Case1：代替D为红色,此时DR肯定是NIL（不然原先D就会违反性质5）。</strong></p>
<p>​    直接把D删除即可。（P的左孩子置为NIL，也就是DR）</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1g9ihl00068j30fu0983yl.jpg" alt="Case1"></p>
<hr>
<p><strong>Case2-1：代替D为黑色，且DR不为空，则DR必为红色。</strong></p>
<p>​    DR变为黑色，且代替D的位置。</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1g9ihn44w48j30gy0bmaaa.jpg"></p>
<hr>
<p><strong>Case2-2 代替D为黑色，且DR为空，也就是为NIL。</strong></p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1g9ihpm6f2xj30gp0b20sz.jpg"></p>
<hr>
<p><strong>Case2-2-1：代替D为黑色，且DR为空，也就是为NIL。DR兄妹节S点为红色，那么P肯定是黑色。</strong></p>
<p>​    此时SL和SR肯定不为NIL，进行左旋从右边借一个黑点补一补</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1g9ihwt9m73j30ic0d7t95.jpg"></p>
<hr>
<p><strong>Case2-2-2：代替D为黑色，且DR为空，也就是为NIL。DR兄妹结点为黑色，则P不确定，SL和SR也不确定，分类讨论。</strong></p>
<p>​    注意此时DR是NIL</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1g9ihzolrw7j30dq0bxmxe.jpg"></p>
<hr>
<p><strong>Case2-2-2-1：代DR为空，也就是为NIL，是黑色的。兄妹节点为黑色，若P不能确定。SL为红色，SR任意（可以为NIL也可以为红）。</strong></p>
<p>​    分析可以得到SL的字节都都是NIL。</p>
<p>为了给P的左路径增加一个黑点，那就只能从右边子树去借用一个了，那就借一个SL吧，反正他是红色的，就算借走了也没事，然后再把SL变成黑色就好了，就到了图1。哎哟坏了，你左边倒是多了一个黑点了，但是我右边也有可能多一个黑点啊(如果P是红色就没有多，但是我们不知道P的颜色)有可能还是不平衡啊。好吧此时SL变成原来P的颜色也就是白色，P变成黑色就好了，如图2.</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1g9ii3ihj0zj30j40e774v.jpg"></p>
<hr>
<p><strong>Case2-2-2-2：DR为空，也就是为NIL，是黑色的。兄妹节点为黑色，若P不能确定。SL为任意（可以为NIL也可以为红），SR红色。</strong></p>
<p>为了给P的左路径增加一个黑点，那就只能从右边子树去借用一个了，SL又不知道颜色(如果是红色的就是上面这样的情况)，只能借S了。左旋一次，就借来了S如图1，此时左边平衡。右边也平 。。。等等，如果P是黑色的话右边路径不久少了一个黑点了？这样也是不平衡的啊，我们要做的是不改变右边路径上黑色点的数量情况下，使左边路径黑点增加一个。好吧，将P和S颜色变一下总行了吧！ 也就是图2.</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1g9ii5vuf1ij30ir0dtq3n.jpg"></p>
<hr>
<p><strong>Case2-2-2-3：DR为空，也就是为NIL，是黑色的。兄妹节点为黑色，P为红色。SL为黑色，SR黑色。</strong></p>
<p>分析可得SL和SR必定为NIL。此时P为红色，S为黑色。那么我们有两种选择了：<br>一种将P改为黑色(为了增加左边黑点），将S改为红色(为了使得右边黑点保持不变)。达到平衡。<br>另外一种以S为支点左旋，此时左边多了一个黑点，右边不变。达到了平衡。</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1g9ii709pgyj30hd0dkjs1.jpg"></p>
<hr>
<p><strong>Case2-2-2-4：DR为空，也就是为NIL，是黑色的。兄妹节点为黑色，P为黑色。SL为黑色，SR黑色。</strong></p>
<p>分析可得SL和SR必定为NIL。这种情况比较简单，我们可以减少一个右边路径黑点，将S改为红色就可以，如右下图。</p>
<p>或者增加左边一个节点，将SL作为根节点，此时达到平衡。什么？你确定？没错啊，左边增加了一个黑点，右边黑点数量没有变。别忘记了，SL和SR如果是黑色的(别问为什么了，看XXX)，那就一定是NIL，那么SL可以当节点？？黑人问号。</p>
<p>所以答案只有一个，那就是右下图。<br><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1g9ii8sggogj30iu0e5dgj.jpg"></p>

        </div>

        
            <section class="post-copyright">
                
                
                
                

            </section>
        
        <section class="post-tags">
            <div>
                <span>Tag(s):</span>
                <span class="tag">
                    
                    
                        <a href="/tags/%E7%BA%A2%E9%BB%91%E6%A0%91/"># 红黑树</a>
                    
                        
                </span>
            </div>
            <div>
                <a href="javascript:window.history.back();">back</a>
                <span>· </span>
                <a href="/">home</a>
            </div>
        </section>
        <section class="post-nav">
            
                <a class="prev" rel="prev" href="/2020/08/27/%E5%BA%8F%E5%88%97%E5%8C%96Serializable/">序列化Serializable</a>
            
            
            <a class="next" rel="next" href="/2020/08/27/%E6%B3%A8%E8%A7%A3/">注解</a>
            
        </section>


    </article>
</div>

        </div>
        <footer id="footer" class="footer">
    <div class="copyright">
        <span>© Mouweng | Powered by <a href="https://hexo.io" target="_blank">Hexo</a> & <a href="https://github.com/Siricee/hexo-theme-Chic" target="_blank">Chic</a></span>
    </div>
</footer>

    </div>
</body>
</html>
